from LL import Node

def fusion(l1, l2):
	return merge(l1, l2)

def merge(a, b):
	r = p = None
	while a!=None or b!=None:
		#need to select the lowest
		if a!=None and b!=None:
			n = min(a.v, b.v)
			#advance
			if a.v<b.v:
				a = a.nx
			else:
				b = b.nx
		#a is the only non-empty list
		elif a!=None:
			n = a.v
			a = a.nx #advance
		#b is the only non-empty list
		else:
			n = b.v
			b = b.nx #advance
		#first result node
		if r==None:
			r = Node(n, None)
			p = r
		#append to the existing result
		else:
			p.nx = Node(n, None)
			p = p.nx #advance
	return r

def mergeSentinel(a, b):
	INF = float("inf")
	r = p = None
	while a.v!=INF or b.v!=INF:
		#insert the smallest (the sentinel will be ignored)
		if a.v<b.v:
			n = a.v
			a = a.nx
		else:
			n = b.v
			b = b.nx
		#first result node (special case)
		if p==None:
			r = Node(n, None)
			p = r
		#append to the existing result
		else:
			p.nx = Node(n, None)
			p = p.nx #advance
	#add a new sentinel
	p.nx = Node(INF, None)
	return r

l1 = Node(1, Node(2, Node(3, None)))
l2 = Node(-1, Node(1.5, Node(2.99, None)))
print fusion(l1, l2)
l1 = Node(1, Node(2, Node(3, Node(float("inf"), None))))
l2 = Node(-1, Node(1.5, Node(2.99, Node(float("inf"), None))))
print mergeSentinel(l1, l2)
